package cn.whdream.datastructure.sort;

import java.util.Arrays;

/**
 * 
 * @author admin 希尔排序
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
		shellSort2(arr);
	}

	/**
	 * 交换法
	 */
	private static void shellSort(int[] arr) {
		int temp;
		for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i - gap; j >= 0; j -= gap) {
					if (arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 插入法
	 */
	private static void shellSort2(int[] arr) {
		int temp;
		for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				temp = arr[j];
				//if (arr[j] < arr[j - gap]) {
					//区别在于两者是 往回减，而非向上加   TODO 记得多敲几把,查查网上攻略；这里讲的不是很清楚
					while(j - gap >= 0 && temp < arr[j - gap]) {
						arr[j] = arr[j - gap];
						j -= gap;
					}
					arr[j] = temp;
				//}
			}
		}
		System.out.println(Arrays.toString(arr));
	}

}
